package node;

import linked.NodeTest;
import sun.reflect.generics.tree.Tree;

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;

/*给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8）    中，按结点数值大小顺序第三小结点的值为4。*/
public class Solutioon {
    public static void main(String[] args) {

    }




    public int TreeDepth(TreeNode root) {
        if (root ==null){
            return 0;
        }
        int leftD=TreeDepth(root.left);
        int rightD = TreeDepth(root.right);
        return  leftD>rightD ? rightD +1: rightD+1;
    }

    public static int NumberOf1Between1AndN_Solution(int n) {
        int sum = 0;
        int a = 1;
        while(a<=n){
            int number = comtainOne(a);
            if (number>0){
                sum+=number;
            }
            a++;
        }
        return sum;
    }

    public static int comtainOne(int n){
        int res =0;
        while(n>0){
            if(n%10 ==1){
                res++;
            }
            n=n/10;
        }
        return res;
    }

    //寻找最小节点，此题目考试知识点为二叉搜索树的深度优先遍历 栈中先加入左子节点

    /*
    一开始思路使用了队列
    TreeNode KthNode(TreeNode pRoot, int k) {
        if (pRoot ==null){
            return null;
        }
        Queue<TreeNode> p = new LinkedList<>();
        pushNode(p,pRoot);
        TreeNode resNode = null;
        for (int a=0;a<k;a++){
            resNode =p.poll();
        }
        return resNode;
    }
    public static void pushNode(Queue<TreeNode> p ,TreeNode node){
        if (node!=null){
            pushNode(p,node.left);
            p.add(node);
            pushNode(p,node.right);
        }
    }*/
}
